package dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。 factorial
 * 给定 n 和 k，返回第 k 个排列。
 * https://leetcode-cn.com/problems/permutation-sequence/
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/1/19 17:53
 */
public class GetPermutation {
    public static void main(String[] args) {
        int n = 4;
        int k = 9;
        System.out.println(getPermutation(n, k));

    }

    public static String getPermutation(int n, int k) {

        int[] item = new int[n];
        backtracking(n, k, item);
        List<Integer> nums = new ArrayList<>();
        String str = "";
        for (int i = 0; i < n; i++) {
            nums.add(i + 1);
        }
        for (int i = n-1; i >= 0; i--) {
            str = str + nums.remove(item[i] - 1);
        }
        return str;
    }

    private static void backtracking(int n, int k, int[] item) {
        if (n > 0) {
            if (n == 1) {
                item[n - 1] = 1;
                return;
            }
            item[n - 1] = k / factorial(n - 1) + 1;
            k = k % factorial(n - 1);
            n = n - 1;
            if (k == 0) {
                item[n] = item[n] - 1;
                for (int i = n - 1; i >= 0; i--) {
                    item[i] = i + 1;
                }
                return;
            }
            backtracking(n, k, item);
        }
    }

    private static int factorial(int n) {
        if (n == 0) {
            return 0;
        }
        int sum = 1;
        for (int i = n; i > 1; i--) {
            sum = sum * i;
        }
        return sum;
    }
}
